package cc.geguo.settree.collectionsdemo;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 作者  Administrator
 * 时间  2017/6/19 9:39
 * 文件  collectiosreview
 * 描述  自己实现一个二分查找
 */
public class HalfSearch {
	public static void main(String[] args) {
//		System.out.println(sortList());
		int pos = halfSearch(sortList(),40);
		System.out.println("pos:"+pos);
	}

	/**
	 * @param list
	 * @param key
	 * 1. 变量 起点 中点 终点
	 * 2. 返回 的是相等的中点值
	 */
	private static int halfSearch(List<Integer> list, Integer key) {
		int min=0,mid,max=list.size()-1;
		// 循环条件是 起点 小于终点
		while (min<max){
			mid = (min+max)>>1;
			int d = key.compareTo(list.get(mid));
			if (d==0){
				return mid;
			}else if (d<0){
				max = mid;
			}else if (d>0){
				min = mid;
			}
		}
		return -1;
	}

	/**
	 * @return 这里会得到一个正序的 集合
	 */
	private static List<Integer> sortList() {
		List<Integer> list = new ArrayList<>();
		// 添加元素
		list.add(30); list.add(20); list.add(50); list.add(10); list.add(40);

		Collections.sort(list);
		return list;
	}


}
